#include <stdio.h>
#include <iostream>

struct Node 
{
	int value;
	Node* next;
};

Node* ReverseNode(Node* head);
//Node* ReverseNodeNonRecursive(Node* head);
void PrintNode(Node* head);
void AddNode(Node** node, int value);

int main()
{
	Node* node = NULL;
	AddNode(&node, 1);
	AddNode(&node, 2);
	AddNode(&node, 3);
	AddNode(&node, 4);
	AddNode(&node, 5);
	Node* resultNode1 = ReverseNode(node);
	PrintNode(resultNode1);
	//Node* resultNode2 = ReverseNodeNonRecursive(node);
	//PrintNode(resultNode2);
	system("pause");
	return 0;
}

Node* ReverseNode(Node* head)
{
	if (NULL == head || NULL == head->next)
	{
		return head;
	}
	Node* temp = ReverseNode(head->next);
	head->next->next = head;
	head->next = NULL;
	return temp;
}

//Node* ReverseNodeNonRecursive(Node* head)
//{
//	if (head == NULL) 
//	{
//		return head;
//	}
//	
//	Node * p = head;
//	Node * previous = NULL;
//	
//	while (p->next) 
//	{
//		p->next = previous;
//		previous = p;
//		p = p->next;
//	}
//	
//	p->next = previous;
//	
//	return p;
//}

void PrintNode(Node* head)
{
	if (head)
	{
		printf("%d\n",head->value);
	}

	if (head->next)
	{
		PrintNode(head->next);
	}
}

void AddNode(Node** node, int value)
{
	if (NULL == *node)
	{
		*node = new Node();
		(*node)->value = value;
		(*node)->next = NULL;
	}
	else
	{
		AddNode(&((*node)->next), value);
	}
}